1. Field of the Invention
This invention relates to improvements in image processing techniques, and more particularly to an efficient, rapid, lossless method of compressing, processing and storing grayscale bitmaps using algorithms that are designed for binary images.
2. Technical Background
In the field of image processing, particularly in reprographic reproduction of an image or in the facsimile transmission of an image, the need for providing grayscale resolution of the image data is becoming of increased importance. Also, recently, with improvements in microprocessors and microcontrollers, and in digital information handling technologies, image data has been read and stored in digital form for processing.
Thus, typically, digital reprographic and image storage systems use a scanner to convert an input document to digital form. Such scanners, in their simplest form, compare the input image on a pixel-by-pixel basis to a predetermined threshold, such that pixels with brightness below the threshold are mapped to "1" (black) and pixels with brightness above the threshold are mapped to "0" (white). In more sophisticated systems, the scanners are capable of discerning various levels of gray in the image, and have a grayscale output, typically 4, 6, or 8 bits per pixel.
While the extension of binary scanners to images having grayscale values intermediate black and white can be realized with only modest technical and cost differences, the differences are much more substantial between binary output devices, such as displays and hard copy producing apparatuses, and those capable of reproducing gray-levels. This is especially true in such hard copy output devices as laser, ionographic, or inkjet printers. Until recently, most such devices were capable of rendering only binary bitmaps. For this reason, continuous-tone images, such as a photograph would be rendered as binary bitmaps for printing using halftoning techniques. For example, if the original were scanned at 300 spi.times.4 bit (16 level) gray, the image could be divided into 4 pixel.times.4 pixel cells, the gray values of the pixels within the cell averaged, and then the 16 pixels in the cell turned on in proportion to the average gray value over the cell; for instance, a gray-level 8 out of 16 would be represented by blacking 8 of the 16 pixels in the cell.
While grayscale hard copy output devices are relatively rare, it has long been known in the bitmap display art that the legibility and apparent image quality of an arbitrarily-shaped image (such as typed characters, lineart, etc.) is improved by the technique of anti-aliasing. Anti-aliasing provides a method of presenting bi-level images on finite-resolution bit-mapped printers or displays with improved image quality by using intermediate graylevels for pixels at the edges of features. More particularly, by this technique, an image can be rendered to a grayscale display of 50 spi.times.5 levels of gray by calculating what the text or image would look like at 200 spi, grouping pixels into 2.times.2 cells, counting up the number of pixels which are on, and mapping this to the gray-value of the 50 spi image. When the image to be rendered is not in vector form (such as typed characters or line-art) but rather is already in high-resolution binary bitmap form, this high-resolution binary to low-resolution grayscale rendering is called inverse halftoning.
Now, recently, hardcopy output devices have begun to appear that are capable of reproducing a few levels of gray, rather than just black or white. One example is a copier/fax that has an 8 bit (256 level) scanner and can reproduce 6 levels of gray in its printout. Even if the original image scanned has no regions of intermediate gray, only black marks on white paper, for example, the apparent image reproduction quality is still improved by grayscale printing because the "jaggies" introduced by the finite spatial resolution of the scanner are softened using gray on partially occluded pixels. If the region does have regions of intermediate gray (such as a photograph or the like), these regions are usually better reproduced by halftone techniques than just mapping each pixel into the limited number of printable gray values. Thus, such digital reprographic systems might be thought of as printing anti-aliased images, whether the input image is monochrome or continuous-tone.
A key problem faced by systems such as the digital copier/fax mentioned above is how to efficiently store the scanned images of pages to support fax or electronic collation functionality. While compression techniques such as CCITT Groups 3 or 4 [G3 or G4] are both lossless and efficient for compressing binary images (i.e., the bitmap produced from a thresholded or half-toned scanned image), they are much less efficient at compressing grayscale data. In typical compression techniques, such as in CCITT G4, the most significant bit of the binary word represents the gray-level of each image pixel. However, such techniques do not efficiently compress the less significant bits that are important in grayscale applications. For these, special techniques exist (e.g., JPEG) which tend to be complex, slow, and sometimes lossy. Custom hardware accelerator ASICs for G4 are far more wide-spread and far less expensive than JPEG.
For example, considering a 2-bit gray printing process, when a multipage document is being copied, it is desirable for the compressed bitmap to be stored in system RAM. If gray-level 3 "11" is black and gray-level 0 "00" is white, then the most-significant-bit will look like the old binary image, and will compress well. However, the least-significant-bit will look like the regular image with a white line drawn around character outlines. This LSB bitmap will not compress as well. Thus, storing the 400.times.2 G3/G4 image takes more than twice the space of the 400.times.1 (MSB) bit image.
The compressed version of the second most significant bitplane is 2 to 3 times as large as the most significant bit plane because the transition from white to black in the original image, once sampled by the scanner, involves the transition from gray-level 0 (binary 00xxx) to gray-level 1 (binary 01xxx), then 2 (binary 10xxx), then gray-level 3 (binary 1xxx). Thus the most-significant bit is 0, then 0, then 1, then 1, while the 2nd-most significant bit is 0, then 1, then 0, then 1 as the scanner sweeps across the white to black edge. The G4 technique uses 1 Huffman code per transition from pixel-on to pixel-off or vice versa, and the 2nd-most-significant bit map has 3 times as many transitions as the edge is swept across.
Other grayscale compression approaches exist. For example, one approach is the so-called "Gray codes" (see, for example, Logic Design with Integrated Circuits, William E. Wickes, (John Wiley & Sons, New York, 1968) p. 14). Another approach is described in the JPEG/MPEG standards. Gray codes have the advantage of being lossless, but would not enable standard G4 compressor/decompresor algorithms/chips to be used without special adaptations; JPEG/MPEG are, in general, lossy and often introduce unwanted artifacts in images of fine text.
Techniques for up-conversion of low-resolution gray to high-resolution binary are also known, and used in products of the Xerox Corporation, like the Docutech or the 7650 scanner, in which the scanner actually scans at 400 spi gray and interpolates to 600 spi binary.
Reference is also made to K. Y. Wong and B. Schatz, in Graphical and Binary Image Processing and Applications, J. C. Stoffel, ed., (Artech House, Dedham Mass., 1982); B. R. Schatz and K. Y. Wong, "Method for improving print quality of coarse-scan/fine-print character reproduction," U.S. Pat. No. 4,124,870, Issued Nov. 7, 1978, assigned to the assignee hereof.